package com.c2b.algorithm.newcoder.heapStackQueue;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * <a href="https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj">最小的K个数</a>
 * <p>
 * 给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。<br>
 * 例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。<br>
 * 数据范围：0≤k,n≤10000，数组中每个数的大小0≤val≤1000<br>
 * 要求：空间复杂度O(n) ，时间复杂度O(nlogk)<br>
 * </p>
 *
 * @author c2b
 * @since 2023/3/14 15:39
 */
public class BM0046GetLeastNumbers_M {
    /**
     * 大根堆
     */
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        if (input == null || input.length == 0 || k <= 0) {
            return new ArrayList<>();
        }
        final ArrayList<Integer> resList = new ArrayList<>();
        if (input.length <= k) {
            for (int i : input) {
                resList.add(i);
            }
            return resList;
        }
        // Java中使用优先级队列实现大根堆。默认就是大根堆
        final PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((Comparator.reverseOrder()));
        // 现在大根堆中维护k个元素
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(input[i]);
        }
        for (int i = k; i < input.length; i++) {
            // 如果新的元素小于堆顶元素，将堆顶元素弹出，将新元素加入大根堆。维护堆中元素为k个
            if (input[i] < priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(input[i]);
            }
        }
        while (!priorityQueue.isEmpty()) {
            resList.add(priorityQueue.poll());
        }
        return resList;
    }

    public static void main(String[] args) {
        BM0046GetLeastNumbers_M bm0046GetLeastNumbers_m = new BM0046GetLeastNumbers_M();
        for (Integer integer : bm0046GetLeastNumbers_m.GetLeastNumbers_Solution(new int[]{4, 5, 1, 6, 2, 7, 3, 8}, 4)) {
            System.out.println(integer);
        }

    }
}
